package zcw.com.lib_leet_code;

import java.util.Arrays;

/**
 * Created by 朱城委 on 2021/7/21.<br><br>
 *
 * 特殊数组的特征值
 */
public class Topic1608 {
    public static void main(String[] args) {
        Topic1608 instance = new Topic1608();

        int[] array = new int[] {3,5};
        System.out.println(instance.specialArray(array));

        array = new int[] {0,0};
        System.out.println(instance.specialArray(array));

        array = new int[] {0,0,0,0,1};
        System.out.println(instance.specialArray(array));

        array = new int[] {0,0,0,0,100};
        System.out.println(instance.specialArray(array));

        array = new int[] {0,4,3,0,4};
        System.out.println(instance.specialArray(array));

        array = new int[] {3,6,7,7,0};
        System.out.println(instance.specialArray(array));
    }

    public int specialArray(int[] nums) {
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] >= nums.length - i && (i == 0 || nums[i - 1] < nums.length - i)) {
                return nums.length - i;
            }
        }
        return -1;
    }

    public int specialArray3(int[] nums) {
        for(int i = 0; i <= nums.length; i++) {
            int counter = 0;
            for(int value : nums) {
                if(value >= i) {
                    counter++;
                }
            }

            if(counter == i) {
                return i;
            }
        }
        return -1;
    }

    public int specialArray2(int[] nums) {
        Arrays.sort(nums);

        int[] result = new int[nums.length + 1];
        Arrays.fill(result, -1);

        for(int i = 0; i <= nums.length; i++) {
            int j = 0;
            while (j < nums.length && nums[j] < i) {
                j++;
            }

            if(j < nums.length) {
                result[i] = nums.length - j;
            }
        }

        for(int i = 0; i < result.length; i++) {
            if(i == result[i]) {
                return i;
            }
        }

        return -1;
    }
}
